#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  vector<int> vec = {5, 4, 6, 8, 2, 1, 3, 7, 9};
  sort(vec.begin(), vec.end());
  for (auto &x : vec) cout << x << ' ';
  cout << endl;

  sort(vec.begin(), vec.end(), [](int a, int b) {
    if (a % 2 != b % 2) {
      return a % 2 == 1;
    }
    return a < b;
  });
  for (auto &x : vec) cout << x << ' ';
  cout << endl;
}